package bTree.LeetCode;

public class 课程表2 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int []res=new int[numCourses];
        int[] degree = new int[numCourses];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int count = 0;
        for (int[] prerequisite : prerequisites) {
            int i = prerequisite[0];
            int i1 = prerequisite[1];
            degree[i]++;
            if (!map.containsKey(i1)) {
                map.put(i1, new ArrayList<>());
                map.get(i1).add(i);
            } else {
                map.get(i1).add(i);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) {
                res[count]=i;
                count++;
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer peek = queue.peek();
            List<Integer> list = map.get(peek);
            if (list != null) {
                for (int i = 0; i < list.size(); i++) {
                    degree[list.get(i)]--;
                    if (degree[list.get(i)] == 0) {
                        queue.add(list.get(i));
                        res[count]=list.get(i);
                        count++;
                    }
                }
            }

            queue.poll();
        }
        if (count == numCourses) {
            return res;
        }
        return new int[]{};
    }
}